package BinaryTree;//给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和
// targetSum 。 
//
// 叶子节点 是指没有子节点的节点。 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：root = [1,2,3], targetSum = 5
//输出：false
// 
//
// 示例 3： 
//
// 
//输入：root = [1,2], targetSum = 0
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 树中节点的数目在范围 [0, 5000] 内 
// -1000 <= Node.val <= 1000 
// -1000 <= targetSum <= 1000 
// 
// Related Topics 树 深度优先搜索 二叉树 👍 699 👎 0


//leetcode submit region begin(Prohibit modification and deletion)


import java.util.Stack;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class hasPathSumI {

    public boolean hasPathSum1(TreeNode root, int targetSum) {
        /**
         * 递归方法
         * */
        if(root == null){
            return false;
        }
        return DLR(root, targetSum);
    }

    //用到 DLR 前序遍历
    boolean DLR(TreeNode node, int targetSum){
        if(node == null){
            //到叶子，不等于目标值则回溯
            return false;
        }
        //当前节点为空，说明到叶子，
        if(node.right == null && node.left == null && targetSum== node.val){
            //到叶子且等于目标值，则存在路径
            return true;
        }
        //看左子树和右子树是否符合要求
        boolean left_flag = false, right_flag = false;
        if(node.left!=null){
            left_flag = DLR(node.left, targetSum - node.val);
        }
        if(node.right!=null){
            right_flag = DLR(node.right, targetSum - node.val);
        }
        return left_flag || right_flag;


    }

    public boolean hasPathSum(TreeNode root, int targetSum) {
        /**
         * 层次遍历迭代不适合
         * 利用栈实现前序遍历
         * */
        if(root==null){
            return false;
        }
        Stack<Object> stack = new Stack<Object>();  //栈保存节点，和当前和
        stack.push(root);
        stack.push(root.val);

        //利用栈实现前序遍历
        while(!stack.isEmpty()){
            // object泛型 注意类型转换
            int sum = (int)stack.pop();  // 当前和
            TreeNode curr = (TreeNode) stack.pop(); //当前节点
            //是叶子节点且符合要求，则true
            if(curr.left==null && curr.right==null && sum==targetSum){
                return true;
            }
            //当进入一个节点时，记录该节点和到该节点的路径和
            if(curr.right!=null){
                stack.push(curr.right);
                stack.push(sum + curr.right.val);
            }
            if(curr.left!=null){
                stack.push(curr.left);
                stack.push(sum + curr.left.val);
            }
        }
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
